package com.xiaobai;

import java.util.ArrayList;
import java.util.List;

public class LeetCodeTest {
    public static int num = 0;
    List<Integer> res = new ArrayList<>();

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"}));
        System.out.println(1 / 2);
        System.out.println(minArray(new int[]{2, 2, 2, 0, 1}));
        System.out.println(hammingWeight(42));
    }

    // you need to treat n as an unsigned value
    public static int hammingWeight(int n) {
        System.out.println(diff(n));
        return num;
    }

    public static String diff(int n) {
        if (n == 0) {
            return "";
        }
        int mod = n % 2;
        if (mod == 1) {
            num++;
        }
        return n % 2 + diff(n / 2);
    }

    public static int minArray(int[] numbers) {
        int l = 0;
        int r = numbers.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (numbers[r] < numbers[mid]) l = mid + 1;
            else if (numbers[r] > numbers[mid]) r = mid;
            else r--;
        }
        return numbers[l];
    }

    public static void rotate(int[] nums, int k) {
        int len = nums.length;
        int temp = 0;
        System.out.println((1 + k) % len);
    }

    /**
     * 最长公共前缀
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        int index = 0;
        String result = "";
        while (true) {
            String temp = "";
            for (int i = 0; i < strs.length; i++) {
                if (index > strs[i].length()) {
                    return result;
                }
                String temp1 = strs[i].substring(0, index);
                if (!temp.isBlank() && !temp.equals(temp1)) {
                    return result;
                }
                temp = temp1;
            }
            index++;
            result = temp;
        }
    }

    public int[] printNumbers(int n) {
        int high = (int) Math.pow(10, n - 1) - 1;
        int[] r = new int[high];
        int low = 0;
        while (low <= high) {
            r[low] = low++;
            r[high] = high--;
        }
        return r;
    }

//    public int[] reversePrint(ListNode head) {
//        Stack<Integer> stack = new Stack<>();
//        while(head != null) {
//            stack.push(head.val);
//            head = head.next;
//        }
//        int[] res = new int[stack.size()];
//        int i = 0;
//        while(!stack.empty()) {
//            res[i++] = stack.pop();
//        }
//        return res;
//    }

    public int[] reversePrint(ListNode head) {
        diff(head);
        int[] resArr = new int[res.size()];
        for (int i = 0; i < resArr.length; i++) {
            resArr[i] = res.get(i);
        }
        return resArr;
    }

    public void diff(ListNode head) {
        if (head == null) {
            return;
        }
        diff(head.next);
        res.add(head.val);
    }

    /**/
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
